#pragma once
#include<iostream>
using namespace std;
#include<vector>

template<class T>
struct HashNode
{
	T _data;
	HashNode<T>* _next;

	HashNode(const T& data)
		: _data(data)
		, _next(nullptr)
	{}
};

template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

template<>
struct HashFunc<string>
{
	size_t operator()(const string& s)
	{
		size_t hashi = 5381;
		for (size_t i = 0; i < s.size(); i++)
		{
			hashi = hashi * 33 ^ s[i];
		}
		return hashi;
	}
};


template<class K, class T,  class KeyOfT, class Hash = HashFunc<K>>
class HashTable;

template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash = HashFunc<K>>
class HasHTableIterator
{
	typedef HashNode<T> Node;
	typedef HasHTableIterator<K, T, Ref , Ptr , KeyOfT, Hash> Self;
private:
	const HashTable<K, T, KeyOfT, Hash>* _v;
	Node* _node;

public:
	HasHTableIterator(Node* node , const HashTable<K, T, KeyOfT, Hash>* hs)
		:_node(node)
		,_v(hs)
	{}

	bool operator!=(const Self& x)
	{
		return _node != x._node;
	}

	Ref operator*()
	{
		return _node->_data;
	}

	Ptr operator->()
	{
		return &(_node->_data);
	}

	Self& operator++()
	{
		if (_v->_n == 0)
		{
			_node == nullptr;
			return *this;
		}

		if (_node == nullptr)
		{
			for (size_t i = 0; i < _v->_table.size(); i++)
			{
				if (_v->_table[i] != nullptr)
				{
					_node = _v->_table[i];
					break;
				}
			}
			return *this;
		}

		KeyOfT kot;
		Hash hs;
		Node* cur = _node;
		if (cur->_next != nullptr)
		{
			_node = cur->_next;
			return *this;
		}
		else
		{
			for (size_t hashi = hs(kot(_node->_data)) % _v->_table.size() + 1; hashi < _v->_table.size(); hashi++)
			{
				if (_v->_table[hashi] != nullptr)
				{
					_node = _v->_table[hashi];
					return *this;
				}
			}
			_node = nullptr;
			return *this;
		}
	}

	Self& operator--()
	{
		if (_v->_n == 0)
		{
			_node = nullptr;
			return *this;
		}

		if (_node == nullptr)
		{
			size_t lasti = -1;
			for (size_t i = 0; i < _v->_table.size(); i++)
			{
				if (_v->_table[i] != nullptr)
					lasti = i;
			}

			Node* cur = _v->_table[lasti];
			while (cur->_next)
			{
				cur = cur->_next;
			}
			_node = cur;
			return *this;
		}
		else
		{
			Hash hs;
			KeyOfT kot;
			size_t hashi = hs(kot(_node->_data)) % _v->_table.size();
			Node* cur = _v->_table[hashi];
			if (_v->_table[hashi] != _node)
			{
				while (cur->_next != _node)
				{
					cur = cur->_next;
				}
				_node = cur;
				return *this;
			}
			else
			{
				size_t previ = -1;
				for (size_t i = 0; i < hashi; i++)
				{
					if (_v->_table[i] != nullptr)
						previ = i;
				}

				if (previ == -1)
				{
					_node = nullptr;
					return *this;
				}
				else
				{
					Node* cur = _v->_table[previ];
					while (cur->_next)
					{
						cur = cur->_next;
					}
					_node = cur;
					return *this;
				}

			}
		}
	}

};


template<class K , class T , class KeyOfT , class Hash>
class HashTable
{
	typedef HashNode<T> Node;
	template<class K, class T, class Ref , class Ptr , class KeyOfT, class Hash>
	friend class HasHTableIterator;
private:
	vector<Node*> _table;
	size_t _n;
public:
	typedef HasHTableIterator<K, T, T& , T* , KeyOfT, Hash> Iterator;
	typedef HasHTableIterator<K, T, const T& , const T* , KeyOfT, Hash> Const_Iterator;

	HashTable()
		:_table(10,nullptr)
		,_n(0)
	{}
	~HashTable()
	{
		for (size_t i = 0; i < _table.size(); i++)
		{
			if (_table[i] != nullptr)
			{
				Node* cur = _table[i];
				Node* next = nullptr;
				while (cur)
				{
					next = cur->_next;
					delete cur;
					cur = next;
				}
				_table[i] = nullptr;
			}
		}
	}

	Iterator Begin()
	{
		if (_n == 0)
			return End();

		for (size_t i = 0; i < _table.size(); i++)
		{
			if (_table[i] != nullptr)
			{
				return Iterator(_table[i], this);
			}
		}

		return End();
	}
	Iterator End()
	{
		return Iterator(nullptr, this);
	}

	Const_Iterator Begin() const 
	{
		if (_n == 0)
			return End();

		for (size_t i = 0; i < _table.size(); i++)
		{
			if (_table[i] != nullptr)
			{
				return Const_Iterator(_table[i], this);
			}
		}

		return End();
	}
	Const_Iterator End() const
	{
		return Const_Iterator(nullptr, this);
	}
	
	Iterator find(const K& key)
	{
		Hash hs;
		KeyOfT kot;
		size_t hashi = hs(key) % _table.size();
		Node* cur = _table[hashi];
		while (cur)
		{
			if (kot(cur->_data) == key)
			{
				return Iterator(cur, this);
			}
			cur = cur->_next;
		}
		
		return End();
	}

	pair<Iterator,bool> insert(const T& data)
	{
		Hash hs;
		KeyOfT kot;

		if (find(kot(data)) != End())
			return make_pair(find(kot(data)),false);

		if (_n / _table.size() == 1)
		{
			vector<Node*> newtable(2 * _table.size());

			for (size_t i = 0; i < _table.size(); i++)
			{
				Node* cur = _table[i];
				while (cur)
				{
					size_t hashi = hs(kot(data)) % newtable.size();
					Node* next = cur->_next;
					cur->_next = newtable[hashi];
					newtable[hashi] = cur;
					cur = next;
				}
			}
			_table.swap(newtable);
		}

		size_t hashi = hs(kot(data)) % _table.size();

		Node* newnode = new Node(data);
		newnode->_next = _table[hashi];
		_table[hashi] = newnode;
		
		++_n;

		return make_pair(Iterator(newnode, this), true);
	}

	bool erase(const K& key)
	{
		Hash hs;
		KeyOfT kot;
		size_t hashi = hs(key) % _table.size();

		Node* cur = _table[hashi];
		Node* prev = nullptr;
		while (cur)
		{
			if (kot(cur->_data) == key)
			{
				if (prev != nullptr)
				{
					prev->_next = cur->_next;
				}
				else
				{
					_table[hashi] = cur->_next;
				}
				delete cur;
				--_n;
				return true;
			}
			prev = cur;
			cur = cur->_next;
		}

		return false;
	}

	size_t size()
	{
		return _n;
	}

	bool empty()
	{
		return _n == 0;
	}


	
};
